package com.leetcode;


import java.util.HashSet;
import java.util.Set;

/**
 * 1016. 子串能表示从 1 到 N 数字的二进制串 (中等)
 * 给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。
 * 子字符串 是字符串中连续的字符序列。
 */
public class LeetCode1016 {

    public static void main(String[] arg0) {
        String s = "0110";
        int n = 4;
        System.out.println("子串能表示从 1 到 " + n + " 数字的二进制串 = " + queryString(s, n));
    }

    public static boolean queryString(String s, int n) {
        boolean res = true;
        for (int i = n; i > 0; i--) {
            String binaryStr = Integer.toBinaryString(i);
            if (!s.contains(binaryStr)) {
                res = false;
                break;
            }
        }
        return res;
    }

    // 哈希表
    public boolean help(String s, int k, int mi, int ma) {
        Set<Integer> set = new HashSet<>();
        int t = 0;
        for (int r = 0; r < s.length(); ++r) {
            t = t * 2 + (s.charAt(r) - '0');
            if (r >= k) {
                t -= (s.charAt(r - k) - '0') << k;
            }
            if (r >= k - 1 && t >= mi && t <= ma) {
                set.add(t);
            }
        }
        return set.size() == ma - mi + 1;
    }

}
